package leetcode;

/**
 * Created by Ghost on 2014/11/6 0006.
 */
public class Sort_List {
    public ListNode seprate(ListNode head){

        if(head==null)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = null;
        while(fast!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next;
            if(fast!=null){
                fast = fast.next;
            }
        }
        pre.next = null;
        return slow;
    }

    public ListNode merge(ListNode head1, ListNode head2){
        ListNode cur = head1;
        ListNode tmp = head2;
        ListNode preCur = null;
        while(cur!=null && tmp!=null){
            if(tmp.val>=cur.val){
                preCur = cur;
                cur = cur.next;
            }
            else {
                if(preCur==null){
                    ListNode a = tmp.next;
                    tmp.next = cur;
                    head1 = tmp;
                    tmp = a;
                    preCur = head1;
                }
                else{
                    ListNode a = tmp.next;
                    tmp.next = cur;
                    preCur.next = tmp;
                    preCur = tmp;
                    tmp = a;
                }
            }
        }
        if(cur == null && tmp!=null){
            if(preCur==null)
                return tmp;
            else{
                preCur.next = tmp;
                return head1;
            }
        }
        else if(cur!=null && tmp == null){
            return head1;
        }
        return head1;
    }

    public int getLen(ListNode head){
        int i=0;
        while(head!=null){
            i++;
            head = head.next;
        }
        return i;
    }
    public ListNode sortList(ListNode head) {
        if(getLen(head)<=1){
            return head;
        }
        ListNode head1 = seprate(head);
        ListNode newHead1 = sortList(head1);
        ListNode newHead2 = sortList(head);
        return merge(newHead1,newHead2);
    }
    public static void main(String[] args){
        Sort_List sortList = new Sort_List();
        ListNode head1 = new ListNode(-3);
        head1.next = new ListNode(1);
        head1.next.next = new ListNode(4);
        head1.next.next.next = new ListNode(5);
        head1.next.next.next.next = new ListNode(8);
        ListNode head = sortList.sortList(head1);
        while(head!=null){
            System.out.print(" "+head.val);
            head = head.next;
        }
    }
}
